home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / oasis / ossxmpls.lha / examples / Tsp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-03-25  |  6.4 KB  |  121 lines
  1. /*======================================================================================================
  2. TSP Solver                                              (C) Copyright Fah-Chun Cheong (Work in Progress)
  3. ======================================================================================================*/
  4. #include                <math.h>
  5. #include                <sys/types.h>
  6. #include                <stdio.h>
  7.  
  8. #define BIGNUM          0x7fffffff
  9. #define N               400
  10. #define W(i,j)          dist[i][j]
  11. #define swap(i,k,tmp)   tmp = v[i]; v[i] = v[k]; v[k] = tmp
  12.  
  13. typedef int             Cost;                                   /* type of intercity costs */
  14.  
  15. Cost                    dist[N][N];                             /* intercity costs matrix */
  16. Cost                    sum;                                    /* cost of partial tour */
  17. Cost                    min;                                    /* minimum cost so far */
  18.  
  19. int                     best[N];                                /* best tour so far */
  20. int                     v[N];                                   /* holds permutation of cities */
  21. int                     n;                                      /* number of cities */
  22. int                     k;                                      /* counting up partial tour */
  23.  
  24. /*======================================================================================================
  25.         Generate a random intercity matrix.
  26. ======================================================================================================*/
  27. void    gen_map()
  28. {
  29.         int     i, j;
  30.         int     b, x = 197;
  31.  
  32.         for (i = 0; i < n; i++)                                 /* go thru row */
  33.             for (j = i+1; j < n; j++) {                         /* go thru column */
  34.                 x = (4757 * x + 1) % 32768;
  35.                 b = 1 + ((x / 16) % 256);
  36.                 W(i,j) = b; W(j,i) = b;
  37.             }
  38.         for (i = 0; i < n; i++) {                               /* go thru row */
  39.             for (j = 0; j < n; j++)                             /* go thru column */
  40.                 printf("%8d", W(i,j));                          /* print out cost */
  41.             putchar('\n');                                      /* next line in matrix */
  42.         }
  43. }
  44.  
  45. /*======================================================================================================
  46.         Dump out solution which is a tour thru all n cities.
  47. ======================================================================================================*/
  48. void    print_tour()
  49. {
  50.         int     i;
  51.  
  52.         min = W(best[n-1], best[0]);                            /* policing ... */
  53.         for (i = 0; i < n-1; i++)
  54.             min = min + W(best[i], best[i+1]);
  55.  
  56.         printf("\n    Best tour:  ");
  57.         for (i = 0; i < n; i++) {
  58.             printf("%4d", best[i]);
  59.             if ((i+1) % 20 == 0) printf("\n                ");
  60.         }
  61.         printf("\n    Min cost = ");
  62.         for (i = 1; i < n; i++) {
  63.             printf("%d + ", W(best[i-1], best[i]));
  64.             if (i % 15 == 0) printf("\n               ");
  65.         }
  66.         printf("%d = %d", W(best[n-1], best[0]), min);          /* from last city to first city */
  67.         printf("\n\n");
  68. }
  69.  
  70. /*======================================================================================================
  71.         Compute optimal tour by exhaustive branch-and-bound search.
  72. ======================================================================================================*/
  73. void    search()
  74. {
  75.         int     tmp;                                            /* temporary loc for swap */
  76.         int     i;
  77.  
  78.         if (k == n-1) {                                         /* all cities visited ? */
  79.             sum += W(v[n-1], v[0]);                             /* wrap around to form cycle */
  80.             if (min > sum) {                                    /* better than previous tour ? */
  81.                 min = sum;                                      /* so update minimum cost so far */
  82.                 for (i = 0; i < n; i++)
  83.                     best[i] = v[i];                             /* save the best solution so far */
  84.             }
  85.             sum -= W(v[n-1], v[0]);                             /* undo cycle */
  86.             return;                                             /* backtrack for more tours */
  87.         }
  88.         for (i = k+1; i < n; i++)                               /* try each remaining cities in turn */
  89.             if (min > sum + W(v[k], v[i])) {                    /* branch only if opportunity is there */
  90.                 sum += W(v[k++],v[i]);                          /* add to partial sum of cost */
  91.                 swap(k, i, tmp);                                /* pick city i */
  92.                 search();                                       /* more cities ! */
  93.                 swap(i, k, tmp);                                /* unpick city i */
  94.                 sum -= W(v[--k],v[i]);                          /* deduct cost of edge to city i */
  95.             }
  96. }
  97.  
  98. /*======================================================================================================
  99.                                     MAIN  PROGRAM
  100. ======================================================================================================*/
  101. void    main(argc, argv)
  102. int     argc;                                                   /* how many arguments ? */
  103. char   *argv[];                                                 /* expect argv[1] to hold n */
  104. {
  105.         int     i, j;
  106.  
  107.         n = atoi(argv[1]);                                      /* get number of cities */
  108.         gen_map();                                              /* generate random matrix */
  109.         for (k = 0; k < n; k++)
  110.             v[k] = k;                                           /* init cities */
  111.         k   = 0;                                                /* start at city v[0] */
  112.         sum = 0;                                                /* zero cost to begin */
  113.         min = BIGNUM;                                           /* minimum over several solutions */
  114.         search();                                               /* exhaustive search */
  115.         print_tour();
  116. }
  117.  
  118. /*======================================================================================================
  119.                                     THE  END
  120. ======================================================================================================*/
  121.